//给定两条线段（表示为起点start = {X1, Y1}和终点end = {X2, Y2}），如果它们有交点，请计算其交点，没有交点则返回空值。 
//
// 要求浮点型误差不超过10^-6。若有多个交点（线段重叠）则返回 X 值最小的点，X 坐标相同则返回 Y 值最小的点。 
//
// 
//
// 示例 1： 
//
// 输入：
//line1 = {0, 0}, {1, 0}
//line2 = {1, 1}, {0, -1}
//输出： {0.5, 0}
// 
//
// 示例 2： 
//
// 输入：
//line1 = {0, 0}, {3, 3}
//line2 = {1, 1}, {2, 2}
//输出： {1, 1}
// 
//
// 示例 3： 
//
// 输入：
//line1 = {0, 0}, {1, 1}
//line2 = {1, 0}, {2, 1}
//输出： {}，两条线段没有交点
// 
//
// 
//
// 提示： 
//
// 
// 坐标绝对值不会超过 2^7 
// 输入的坐标均是有效的二维坐标 
// 
//
// Related Topics 几何 数学 👍 90 👎 0


package LeetCode.editor.cn;

/**
 * @author ldltd
 * @date 2025-09-07 21:58:23
 * @description 面试题 16.03.交点
 */
public class IntersectionLcci{
	 public static void main(String[] args) {
	 	 //测试代码
	 	 IntersectionLcci fun=new IntersectionLcci();
	 	 Solution solution = fun.new Solution();

	 }
	 
//力扣代码
//leetcode submit region begin(Prohibit modification and deletion)
class Solution {
		 //也可以用线性代数向量求解，但是太难了不会
	double[] ans = new double[0];

	public double[] intersection(int[] start1, int[] end1, int[] start2, int[] end2) {
		int x1 = start1[0], y1 = start1[1];
		int x2 = end1[0], y2 = end1[1];
		int x3 = start2[0], y3 = start2[1];
		int x4 = end2[0], y4 = end2[1];

		// 判断 (x1, y1)~(x2, y2) 和 (x3, y3)~(x4, y4) 是否平行
		if ((y4 - y3) * (x2 - x1) == (y2 - y1) * (x4 - x3)) {
			// 若平行，则判断 (x3, y3) 是否在「直线」(x1, y1)~(x2, y2) 上
			if ((y2 - y1) * (x3 - x1) == (y3 - y1) * (x2 - x1)) {
				// 判断 (x3, y3) 是否在「线段」(x1, y1)~(x2, y2) 上
				if (inside(x1, y1, x2, y2, x3, y3)) {
					update(x3, y3);
				}
				// 判断 (x4, y4) 是否在「线段」(x1, y1)~(x2, y2) 上
				if (inside(x1, y1, x2, y2, x4, y4)) {
					update(x4, y4);
				}
				// 判断 (x1, y1) 是否在「线段」(x3, y3)~(x4, y4) 上
				if (inside(x3, y3, x4, y4, x1, y1)) {
					update(x1, y1);
				}
				// 判断 (x2, y2) 是否在「线段」(x3, y3)~(x4, y4) 上
				if (inside(x3, y3, x4, y4, x2, y2)) {
					update(x2, y2);
				}
			}
			// 在平行时，其余的所有情况都不会有交点
		} else {
			// 联立方程得到 t1 和 t2 的值
			double t1 = (double) (x3 * (y4 - y3) + y1 * (x4 - x3) - y3 * (x4 - x3) - x1 * (y4 - y3)) / ((x2 - x1) * (y4 - y3) - (x4 - x3) * (y2 - y1));
			double t2 = (double) (x1 * (y2 - y1) + y3 * (x2 - x1) - y1 * (x2 - x1) - x3 * (y2 - y1)) / ((x4 - x3) * (y2 - y1) - (x2 - x1) * (y4 - y3));
			// 判断 t1 和 t2 是否均在 [0, 1] 之间
			if (t1 >= 0.0 && t1 <= 1.0 && t2 >= 0.0 && t2 <= 1.0) {
				ans = new double[]{x1 + t1 * (x2 - x1), y1 + t1 * (y2 - y1)};
			}
		}
		return ans;
	}

	// 判断 (xk, yk) 是否在「线段」(x1, y1)~(x2, y2) 上
	// 这里的前提是 (xk, yk) 一定在「直线」(x1, y1)~(x2, y2) 上
	public boolean inside(int x1, int y1, int x2, int y2, int xk, int yk) {
		// 若与 x 轴平行，只需要判断 x 的部分
		// 若与 y 轴平行，只需要判断 y 的部分
		// 若为普通线段，则都要判断
		return (x1 == x2 || (Math.min(x1, x2) <= xk && xk <= Math.max(x1, x2))) && (y1 == y2 || (Math.min(y1, y2) <= yk && yk <= Math.max(y1, y2)));
	}

	public void update(double xk, double yk) {
		// 将一个交点与当前 ans 中的结果进行比较
		// 若更优则替换
		if (ans.length == 0 || xk < ans[0] || (xk == ans[0] && yk < ans[1])) {
			ans = new double[]{xk, yk};
		}
	}

}
//leetcode submit region end(Prohibit modification and deletion)

}
